from heapq import *


def min_k_in_matrix(matrix, k):
    m = len(matrix)
    n = len(matrix[0])

    min_heap = []

    for i in range(min(k, m)):
        heappush(min_heap, (matrix[i][0], 0, i))

    num = 0
    for i in range(k):
        num, col, row = heappop(min_heap)
        if col + 1 < n:
            heappush(min_heap, (matrix[row][col + 1], col + 1, row))

    return num


print(min_k_in_matrix(matrix=[
    [1, 5, 9],
    [10, 11, 13],
    [12, 13, 15]
],
    k=2))
